package com.mgq.algorithm.greedy;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author MaGuangQi
 * 给定一个字符串数组，找到一种拼接方式，使得把所有字符串拼接起来之后形成的字符串具有最小的字典序
 * 注意:最后形成的是最小字典序
 * aaabbab
 * 例如字符串b和ba,最小的字典序是 bab.
 * ab 和ba abba
 * 贪心策略。 1.按照字符串的字典序的比较 字典序小的排前面， 我们最终发现结论是错误的。
 *          比如 b和ba，按照字典序大小 b的字典序小于ba，最终是bba.(结论是错误）
 *          2. 按照 a.b<=b.a 把a放前面,否则把b放前面
 *字典序
 * @date 2022-01-05 09:41
 **/
public class DictionarySort {

    public static String dicSort(String[] str) {
        String res = "";
        Arrays.sort(str, new DictionaryComparator());
        for (int i = 0; i < str.length; i++) {
            res += str[i];
        }
        return res;
    }

    public static void main(String[] args) {
        String[] str = {"ab", "ba","b","aa"};
        System.out.println(dicSort(str));
    }
}

class DictionaryComparator implements Comparator<String>{

    @Override
    public int compare(String a, String b) {
        //贪心策略. 就是按照 a.b<=b.a时, a放前面,否则把b放前面
        //对字符串来说,这个就返回的是他们的字典序
        //比如 "ab"<"ba"
        return (a+b).compareTo(b+a);
    }
}

